package scenic.study.datastructure.tree;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * Created by scenic on 2015/5/3.
 */
public class BinaryTree {
    private BinaryTreeNote root;

    public static void main(String args[]) {
        new BinaryTree().run();
    }

    public void run() {
//        test_makeTree1();
//        test_makeTree2();
//        test_makeTree3();
        test_makeTree4();
        System.out.println(root.preOrder());
        System.out.println(root.inOrder());
        System.out.println(root.postOrder());
        System.out.println(root.levelOrder());
        System.out.println("===========================");
        root.levelOrderPrint();

    }

    private void test_makeTree4() {

        root = new BinaryTreeNote(8);
        root.setLChild(new BinaryTreeNote(8)).setLChild(new BinaryTreeNote(1));
        root.setRChild(new BinaryTreeNote(2)).setRChild(new BinaryTreeNote(1)).setRChild(new BinaryTreeNote(2));
        root.getLChild().setRChild(new BinaryTreeNote(6)).setRChild(new BinaryTreeNote(5));
        root.getLChild().getRChild().setLChild(new BinaryTreeNote(5));
        root.getRChild().setLChild(new BinaryTreeNote(9));
        root.getRChild().getRChild().setLChild(new BinaryTreeNote(7));
    }

    private void test_makeTree3() {
        BinaryTreeNote root = new BinaryTreeNote(8);
        BinaryTreeNote l = new BinaryTreeNote(5);
        BinaryTreeNote r = new BinaryTreeNote(2);

        root.setLChild(l);
        root.setRChild(r);

        r.setLChild(new BinaryTreeNote(9));
        r.setRChild(new BinaryTreeNote(7));

        l.setLChild(new BinaryTreeNote(1));
        r = new BinaryTreeNote(6);
        l.setRChild(r);

        r.setLChild(new BinaryTreeNote(8));
        r.setRChild(new BinaryTreeNote(5));

    }

    private void test_makeTree2() {
        {
            String[] tree1 = new String[]{
                    "-", "+", "/", "a", "x", "e", "f"
            };

            String[] tree2 = new String[]{
                    "%", "b", "c"
            };

            BinaryTreeNote xTree = null;

            for (int i = 0; i < tree1.length; i++) {
                BinaryTreeNote temp = add(root, tree1[i]);
                if (i == 0) {
                    root = temp;
                }
                if (temp.getData().equals("x")) {
                    xTree = temp;
                }
            }

            BinaryTreeNote noteTree2 = createTreeByArrayAndReturnRootNote(tree2);

            xTree.setLChild(noteTree2);

            xTree.setRChild(new BinaryTreeNote("d"));
        }
    }

    private void test_makeTree1() {
        String[] tree1 = new String[]{
                "-", "+", "/", "a", "x", "e", "f"
        };

        String[] tree2 = new String[]{
                "-", "b", "c"
        };

        BinaryTreeNote xTree = null;

        for (int i = 0; i < tree1.length; i++) {
            BinaryTreeNote temp = add(root, tree1[i]);
            if (i == 0) {
                root = temp;
            }
            if (temp.getData().equals("x")) {
                xTree = temp;
            }
        }

        BinaryTreeNote noteTree2 = createTreeByArrayAndReturnRootNote(tree2);

        xTree.setLChild(noteTree2);

        xTree.setRChild(new BinaryTreeNote("d"));
    }

    public BinaryTreeNote createTreeByArrayAndReturnRootNote(Object[] objects) {
        BinaryTreeNote root = new BinaryTreeNote(objects[0]);
        for (int i = 1; i < objects.length; i++) {
            add(root, objects[i]);
        }
        return root;
    }

    /**
     * 顺序的横向的增加
     *
     * @param object
     */
    public BinaryTreeNote add(BinaryTreeNote root, Object object) {

        //create new note
        BinaryTreeNote newTree = new BinaryTreeNote(object);

        if (root != null) {
            BinaryTreeNote cursor = root;
            BinaryTreeNote last;

            while (cursor != null) {
                last = cursor;

                //get the left and right child
                BinaryTreeNote lChild = cursor.getLChild();
                BinaryTreeNote rChild = cursor.getRChild();

                if (lChild == null && rChild == null) {
                    //如果条件成立，说明已经是叶子节点了

                    newTree.setParent(last);
                    last.setLChild(newTree);
                    cursor = null;
                } else if (lChild != null && rChild == null) {
                    newTree.setParent(last);
                    last.setRChild(newTree);
                    cursor = null;
                } else {
                    //以上条件都不满足的话，需要往下进行遍历

                    if (lChild.getLChild() != null && lChild.getRChild() != null &&
                            (rChild.getLChild() == null | rChild.getRChild() == null)) {
                        cursor = rChild;
                    } else {
                        cursor = lChild;
                    }
                }
            }
        }
        return newTree;
    }

    int index = 0;

    @Test
    public void testDD() {
        String aa = "if you are interested in HiApp,please contact Xingxuan Li,Email:xxuan-li@hnair.com";
        List<String> list = new ArrayList<>();
        aa.chars().forEach(a -> {
            index++;
            int code = (char) a;
            String valueCode = code + "";
            if (code >= 100 && code < 999) {

            } else if (code < 100 && code > 0) {
                valueCode = "0" + code;
            } else {
                System.err.println("error=== " + code);
            }

            list.add(index + valueCode);


        });


        int aaaIndex = 0;
        for (int i = 0; i < list.size(); i++) {
            int index = new Random().nextInt(list.size());
            String a = list.get(index);
            list.remove(index);
            System.out.print(a + "," + "\t");
            aaaIndex++;
            if (aaaIndex % 10 == 0) {
                System.out.println();
            }
            i--;

        }


        int values[] = {
                80099,	16114,	63108,	25032,	31044,	59069,	39099,	13110,	34101,	66120,
                19116,	72105,	70045,	38032,	41110,	12105,	75110,	27105,	1105,	9114,
                67117,	20101,	21100,	11032,	79046,	32112,	5111,	6117,	45116,	22032,
                61097,	65120,	49110,	15101,	82109,	50103,	54110,	17101,	46032,	4121,
                76097,	7032,	57105,	2102,	58044,	8097,	44099,	73064,	81111,	43097,
                30112,	14116,	60109,	74104,	77105,	35097,	64058,	29112,	55032,	33108,
                71108,	40111,	47088,	52117,	56076,	68097,	37101,	78114,	24110,	53097,
                69110,	48105,	18115,	26072,	3032,	42116,	62105,	51120,	28065,	10101,
                23105,	36115
        };

        //请将上面数组的内容有序的存入二叉树中，然后由小到大遍历二叉树，把遍历到的数值取后三位转化成字符输出


        //第二小题：
        //请使用中序遍历打印二叉树，并且把节点数据的后三位转化成字符打印出来

        //第三小题
        // 把二叉树转化成一个双向有序的链表


        System.out.println();

        BinaryTreeNote note = new BinaryTreeNote();
        for (int a : values) {
            addByOrder(a, note);
        }
        note.inOrder().forEach(v -> System.out.print((char) (Integer.parseInt(v.toString()) % 1000)));

    }



    private void addByOrder(int value, BinaryTreeNote root) {
        BinaryTreeNote cursor = root;
        while (cursor != null) {
            if (cursor.getData() == null) {
                cursor.setData(value);
                break;
            } else {
                BinaryTreeNote newNode = new BinaryTreeNote(value);
                newNode.setParent(cursor);
                int data = (int) cursor.getData();
                BinaryTreeNote left = cursor.getLChild();
                BinaryTreeNote right = cursor.getRChild();
                if (value > data) {
                    if (right == null) {
                        cursor.setRChild(newNode);
                    } else {
                        addByOrder(value, right);

                    }
                } else {
                    if (left == null) {
                        cursor.setLChild(newNode);
                    } else {
                        addByOrder(value, left);
                    }

                }
                break;
            }
        }

    }


}
